package com.datastructure.test.longestuniquesubsequence2;


import java.util.*;
import java.util.stream.Collectors;

public class LongestUniqueSubsequence {

    public static void main(String[] args) {
        LongestUniqueSubsequence longestUniqueSubsequence = new LongestUniqueSubsequence();
        ArrayList<String> strs = new ArrayList<>();
        strs.add("aaa");
        strs.add("bbb");
        strs.add("bbb");
        strs.add("aaa");
        int i = longestUniqueSubsequence.longestUniqueSubsequence(strs);
        System.out.println(i);
    }

    public int longestUniqueSubsequence (ArrayList<String> strs) {
        // write code here
        HashMap<String,Integer> hashMap = new HashMap<>();
        for (String str : strs) {
            if(hashMap.containsKey(str)){
                hashMap.computeIfPresent(str,(key,value) -> value=value+1);
            } else {
                hashMap.put(str,1);
            }
        }
        if (!hashMap.containsValue(1)) {
            return -1;
        }
        HashMap<Integer,ArrayList<String>> map = new HashMap<>();
        ArrayList<String> tempList;
        int length;
        for (String str : strs) {
            length = str.length();
            if(map.containsKey(length)){
                tempList= map.get(length);
                tempList.add(str);
            } else {
                tempList=new ArrayList<>();
                tempList.add(str);
                map.put(length,tempList);
            }
        }
        if (map.size()>=2) {
            List<Integer> collect = map.keySet().stream().sorted().collect(Collectors.toList());
            tempList = map.get(collect.get(collect.size()-1));
            if(tempList.size()==1){
                return tempList.get(0).length();
            } else {
                return compute(tempList,false);
            }
        } else {
            return compute(strs,true);
        }
    }

    private int compute(ArrayList<String> strs,boolean flag) {
        Set<Character> set = new HashSet<>();
        char[] chars;
        for (String str : strs) {
            chars = str.toCharArray();
            for (char c : chars) {
                set.add(c);
            }
        }
        if(set.size()==1){
            return -1;
        }
        int length = strs.get(0).length();
        String tempString;
        int maxLength = length;
        for (int i = 0; i < strs.size(); i++) {
            tempString = strs.get(i);
            chars = tempString.toCharArray();
            Arrays.sort(chars);
            strs.set(i,new String(chars));
        }
        for (int i = length; i >=0; i--) {
            tempString=strs.get(0).substring(0,i);
            if(isContains(tempString,strs)){
                if(i==length){
                    return length;
                }
            }else {
                maxLength = Math.min(i, maxLength);
            }
        }
        if(maxLength< length){
            if(flag){
                return maxLength;
            } else {
                return length;
            }
        }
        return maxLength;
    }

    private boolean isContains(String tempString, ArrayList<String> strs) {
        String s;
        for (int i = 1; i < strs.size(); i++) {
            s = strs.get(i);
            if(s.equals(tempString)){
                return false;
            }
        }
        return true;
    }

    public int longestUniqueSubsequence1 (ArrayList<String> strs) {
        // write code here
        strs.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length()-o2.length();
            }
        });
        int cnt  =-1;
        for(int i=0;i<strs.size();i++){
            int flag =0;
            for(int j=0;j<strs.size();j++){
                if(strs.get(j).contains(strs.get(i))&&i!=j){

                    flag=1;break;
                }
            }
            if(flag==0){
                if(cnt<strs.get(i).length()){
                    cnt = strs.get(i).length();
                }
            }
        }
        return cnt;
    }
}
